// 因为这里的innerSort写的不好，所以自己写一个
#include <stdio.h>
#include <windows.h>

// 输出
void traverse(int array[],int length){
    for(int a=0;a<length;a++){
        printf("%d ",array[a]);
    }
    printf("\n");
}

// 交换两个数字
void swaps(int array[],int i,int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

// =====================直接插入排序==========================
void insertSort(int array[],int length){
    int num = 0;
    for(int a=1;a<length;a++){
        int temp = array[a];
        int j = a;

        for(;temp<array[j-1];--j){
            array[j] = array[j-1];
            ++num;
        }

        array[j] = temp;

        // 打印每次排序后的顺序
        traverse(array,10);
        printf("===============================\n");
        ++num;
    }
       
    printf("共执行了%d次 \n",num);
}

// =========================折半插入排序=================================
void binaryInsertSort(int array[],int length){
    int num = 0;
    for(int i=1;i<length;i++){
        // 前面有序的部分
        int low = 0;
        int high = i-1;

        // 通过折半，找到要插入的位置   
        if(array[i]>=array[high]){
            low = i;
        }else if(array[i]<=array[0]){
            low = 0;
        }else{
            while(low <= high){
                // 右移等价于除以2；效率比除法高
                int mid = (low + high) >> 1;
                
                if(array[i] <= array[mid]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
                ++num;
            }
        }

        int temp = array[i];
        for(int j=i;j>low;j--){
            array[j] = array[j-1];
            ++num;
        }
        array[low] = temp;
        // 打印每次排序后的顺序
        traverse(array,10);
        printf("===============================\n");
        ++num;
    }
    printf("共执行了%d次 \n",num);
}

// =================希尔排序============================
void shellSort(int array[],int length){
    int num = 0;

    int gap = length;
    // 决定要循环多少次完成排序;决定划分多少列
    while(gap > 0 ){
        gap = gap >> 1;

        // 对每一列进行排序
        for(int col = 0;col<gap;col++){
            // 对本列进行排序，使用插入排序;begin是这一列取出来准备排序的数
            for(int begin = col+gap;begin<length;begin+=gap){
                int temp = array[begin];
                int j = begin;
                
                // 这里表示temp与前一位进行比较(直接插入排序的思想)
                for(;temp<array[j-gap]&&j>col;j-=gap){
                    array[j] = array[j-gap];

                    ++num;
                }
                array[j] = temp;

                // 打印每次排序后的顺序
                traverse(array,10);   
                printf("===============================\n");
                ++num;
            }
            ++num;
        }
        ++num;
    }

    printf("共执行了%d次 \n",num);
}

// ========================冒泡排序(改进版本)======================
void bubbleSort(int array[],int length){
    int num = 0;

    for(int i=0;i<length-1  ;++i){
        // 这个值是true，证明没有发生交换，那么就说明已经是有序的。这个要基于如下的int j=i，这一段说明，每次比较，从大循环的值开始比，因为前面因为之前的比较已经有序
        boolean isSort = true;
        for(int j=i+1;j<length;++j){
            if(array[j]<array[i]){
                isSort = false;
                int temp=array[j];
                array[j] = array[i];
                array[i] = temp;
            }
            traverse(array,10);
            printf("===============================\n");
            
            ++num;
        }
        if(isSort){
            break;
        }
        ++num;
    }

    printf("共执行了%d次 \n",num);
}

// ==================快速排序==========================
// 递归方法
void quickSort_Recursion(int array[],int begin,int end){
    if(begin >= end){
        return;
    }
    int temp = array[begin];
    // 左指针
    int i = begin;
    // 右指针
    int j = end;
    // 左右指针一样时，跳出循环
    while(i != j){
        // 右指针所指数字比基准大就继续移动
        while(array[j] >= temp && j>i ){
            j--;
        }
        // 左指针所指数字比基准小就继续移动
        while(array[i] <= temp && j>i){
            i++;
        }
        // 交换的情况，也就是右指针所指数字小于基准，左指针所指数字大于基准
        if(j > i){
           swaps(array,i,j);

            traverse(array,10);
            printf("===============================\n");
        }
    }
    array[begin] = array[i];
    array[i] = temp;
    
    traverse(array,10);
    printf("===============================\n");
    quickSort_Recursion(array,begin,i-1);
    quickSort_Recursion(array,i+1,end);
}

//====================选择排序========================
void selectionSort(int array[],int length){
    int left = 0;
    int right = length-1;
    while(left < right){
        int min = left;
        int max = right;
        // 找到最大最小值在哪里
        for(int i=left;i<=right;++i){
            if(array[i]>array[max]){
                max = i;
            }else if(array[i]<array[min]){
                min = i;
            }
        }

        swaps(array,left,min);
        swaps(array,right,max);
        
        ++left;
        --right;
        traverse(array,10);
        printf("===============================\n");
    }
}

//===================归并排序====================
// 将左右的n块逐步给拼起来
void merge(int array[],int start,int mid,int end){
    // 先对左边排序，再对右边排序，然后合起来
    int left = start;
    int right = mid +1;
    
    // 左边最大的小于右边最小的不变
    // 左边最小的大于右边最大的
    if(array[left] > array[end]){
        for(int i=0;i<end-mid;i++){
            if((mid+1+i) >= end){
                swaps(array,left+i,end);
                traverse(array,10);
            }else{
                swaps(array,left+i,mid+1+i);
                traverse(array,10);
            }
        }
    }else if(! (array[mid] < array[right])){
        int tempArray[end-start+1];
        int i=0;
        for(left;left<=mid;left++){
            while(right<=end){
                if(array[left]>array[right]){
                    // swaps(array,left,right);
                    // traverse(array,10);
                    tempArray[i++] = array[right];
                    right++;
                }else{
                    // 左边的要加1与右边的进行比较   
                    break;
                }
            }
            tempArray[i++] = array[left];
        }

        for(int a=0;a<end-start+1;a++){
            array[start+a] = tempArray[a];
        }
        traverse(array,10);
    }

}
//将整个数组分成左右各n块
void mergeSort(int array[],int start,int end){
    if(start < end){
        int mid = (start + end) >> 1;
        mergeSort(array,start,mid);
        mergeSort(array,mid+1,end);
        merge(array,start,mid,end);
    }
}

//====================堆排序1=======================
/**
 * 构造二叉堆和重新构造二叉树
 * 将构造二叉树的思想与重新构造二叉树合二为一，都是将自己作为顶级节点，然后一步一步向下走，也就是和子节点比较
*/
void siftDown(int index,int length,int array[]){
    // 4,3,2,1,0
    int i=index;
    //9,7,5,3,1;这个表示左节点
    int left=2*i + 1;
    int temp = array[i];   
    while(left<length){
        // 如果右节点比左节点大，则用右节点和i所代表的数进行比较
        if( (left<length-1) && (array[left]<array[left+1]) ){
            left++;
        }
        if(temp < array[left]){
            array[i] = array[left];
            i = left; 
            // 等价于left = 2*i+1，这样写语义更好，因为i=left，所以是下面的写法
            left = 2*left+1;
        }else{
            break;
        }
    }
    // 这个i是上一个的left值
    array[i] = temp;
    traverse(array,10);
}

void heapSort(int array[],int length){
    // 构建堆;这里暂时不知道怎么改成i++，因为取出来的数据，是作为顶级节点的存在，i++的话就是作为子节点的存在，要向上查询
    for(int i=length/2-1; i>=0; i--){
        siftDown(i,length,array);
    }
    traverse(array,10);

    // 重新构建，是在二叉堆的基础之上的
    for(int i=length-1;i>0;i--){
        // 将最大值放在最后
        swaps(array,0,i);
        // 对剩余的数(除了最大值)重新构建堆
        siftDown(0,i,array);
    }
    traverse(array,10);
}

//====================堆排序2=======================
/**
 * 构建堆，每一个插入的节点都是子节点(不用考虑是左还是右，每一个插入节点按顺序来就行)，然后与其父节点进行对比替换，然后更换子节点与父节点的索引，循环到阶段结束
 */
// void buildHeap(int length,int array[]){
//     for(int i=0;i<length;i++){
//         int currentIndex = i;
//         int fatherIndex = (currentIndex -1) /2;
//         while(fatherIndex>=0 && array[currentIndex] > array[fatherIndex]){
//             swaps(array,currentIndex,fatherIndex);
//             // 当前索引指向父索引
//             currentIndex = fatherIndex;
//             fatherIndex = (currentIndex -1) /2;
//         }
//     }
// }

/**
 * 重新构建堆，
 * 当前索引一直是0，也就是顶级节点，所以需要与左右节点进行对比，直到顶级的节点找到合适的位置
 */
// void heapify(int array[],int index,int length){
//     int left = 2*index +1;
//     int right = 2*index +2;
//     while(left < length){
//         int largestIndex;
//         if(array[left] < array[right] && right < length){
//             largestIndex = right;
//         }else{
//             largestIndex = left;
//         }
//         if(array[index] > array[largestIndex]){
//             largestIndex = index;
//         }
//         if(index == largestIndex){
//             break;
//         }
//         swaps(array,largestIndex,index);
//         index = largestIndex;
//         left = 2*index + 1;
//         right = 2*index + 2;
//     }
// }

// void heapSort(int array[],int length){
//     // 构建堆
//     buildHeap(length,array);
//     traverse(array,10);
//     while(length >1){
//         swaps(array,0,length-1);
//         length--;
//         heapify(array,0,length);
//     }
//     traverse(array,10);
// }

//====================堆排序3=======================
/**
 * 构造二叉堆
 * 当前索引一直是累加的，对应的一直在堆的子节点，所以需要循环找到其父节点，一直往上将数据排序 
*/
// void siftDown(int index,int length,int array[]){
//     // 当前索引
//     int i=index;
//     // 左子节点
//     int left=2*i + 1;
//     int temp = array[i];   
//     while(left > 0){
//         // 比较父子节点，选择大的作为父节点
//         if( left+1 < length && array[left] < array[left+1]){
//            ++left;
//         }
//         if(array[i] < array[left]){
//             swaps(array,i,left);
//             traverse(array,10);
//             i = (i-1)>>1;
//             left = 2*i+1;
//         }else{
//             break;
//         }
//     }
// }

// void heapSort(int array[],int length){
//     /**
//      * 构建堆
//      * 给定一个索引，根据二叉堆的特点，其父结点索引：(i-1)/2 ，左子节点2*i+1，右子节点2*i+2
//      * 所以一个数组，只对其一半进行处理，就可以对所有的数进行处理
//      */
//     for(int i=0; i<length/2; i++){
//         siftDown(i,length,array);
//     }
//     traverse(array,10);
//     for(int i=0;i< length;i++){
//         // 将最大值放在最后
//         swaps(array,0,length -1-i);
//         // 对剩余的数(除了最大值)重新构建堆
//         heapify(array,0,length-1-i);
//     }
//     traverse(array,10);
// }

int main(){
    system("chcp 65001 > nul");

    //3,10,13,27,38,49,49,65,76,97
    // printf("================直接插入排序================== \n");
    // int array1[] = {3,10,13,27,38,49,49,65,76,97};
    // traverse(array1,10);
    // insertSort(array1,10);

    //97,76,65,49,49,38,27,13,10,3
    // printf("================折半插入排序================== \n");
    // int array2[] = {3,10,13,27,38,49,49,65,76,97};
    // traverse(array2,10);
    // binaryInsertSort(array2,10);

    // // 3,49,38,65,97,76,13,27,49,10
    // printf("================希尔排序================== \n");
    // int array3[] = {3,10,13,27,38,49,49,65,76,97};
    // traverse(array3,10);
    // shellSort(array3,10);

    // printf("================冒泡排序================== \n");
    // int array4[] = {97,76,65,49,49,38,27,13,10,3};
    // traverse(array4,10);
    // bubbleSort(array4,10);

    // printf("================快速排序================== \n");
    // int array5[] = {3,49,38,65,97,76,13,27,49,10};
    // traverse(array5,10);
    // quickSort_Recursion(array5,0,9);

    // printf("================选择排序================== \n");
    // int array6[] = {3,49,38,65,97,76,13,27,49,10};
    // traverse(array6,10);
    // selectionSort(array6,10);  

    // printf("================归并排序================== \n");
    // int array7[] = {3,49,38,65,97,76,13,27,49,10};
    // traverse(array7,10);
    // mergeSort(array7,0,9);

    // printf("================堆排序================== \n");
    // int array8[] = {3,49,38,65,76,97,13,27,49,10};
    // traverse(array8,10);
    // heapSort(array8,10);

    // printf("================基数排序================== \n");


    // printf("================计数排序================== \n");


    // printf("================桶排序================== \n");
    return 0;
}